package leetcode.editor.vscdev.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class lc17 {
    public static void main(String[] args) {
        lc17 instance = new lc17();
        Solution solution = instance.new Solution();
        solution.letterCombinations("23");
    }
    // 回溯法
    class Solution {
        // 数字-字符映射表
        private final String[] letterMap = {
                "",
                "",
                "abc",
                "def",
                "ghi",
                "jkl",
                "mno",
                "pqrs",
                "tuv",
                "wxyz"
        };
        private List<String> res = new ArrayList<String>();
        public List<String> letterCombinations(String digits) {
            if (digits == null || digits.length() == 0) {
                return res;
            }
            backtracking(digits, 0);
            return res;
        }
        // 用于高频字符串拼接
        StringBuilder sb = new StringBuilder();
        /* index 层数
         * s 传入的数字字符串
         */
        public void backtracking(String s, int index) {
            if (index == s.length()) {
                // 终止条件
                res.add(sb.toString());
                return;
            }
            // 获取数字对应字符串(s.charAt(index) - '0'获取输入的数字索引)
            String str = letterMap[s.charAt(index) - '0'];
            // 进行处理
            for (int i = 0; i < str.length(); i++) {
                sb.append(str.charAt(i));
                backtracking(s, index + 1);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
    // 双重for循环迭代,时间复杂度O(n^2)
    class Solution1 {
        public List<String> letterCombinations(String digits) {
            List<String> result = new ArrayList<>();
            int n = digits.length(); // 获取数字字符串长度
            if (n == 0){
                return result;
            }
            // 初始化映射列表
            Map<Character, List<String>> map = new HashMap<>();
            map.put('2', Arrays.asList("a","b","c"));
            map.put('3', Arrays.asList("d","e","f"));
            map.put('4', Arrays.asList("g","h","i"));
            map.put('5', Arrays.asList("j","k","l"));
            map.put('6', Arrays.asList("m","n","o"));
            map.put('7', Arrays.asList("p","q","r","s"));
            map.put('8', Arrays.asList("t","u","v"));
            map.put('9', Arrays.asList("w","x","y","z"));
            // 结果列表初始化为第一个数字字符对应列表
            result = map.get(digits.charAt(0));
            if (n == 1){
                return result;
            }
            // 从第二个字符开始处理
            int i = 1;
            while (i < n){
                List<String> temp = new ArrayList<>();
                for (String s1 : result) {
                    for (String s2 : map.get(digits.charAt(i))) {
                        temp.add(s1+s2);
                    }
                }
                // 更新为temp,会使之前的第一个字符对应列表消失
                result = temp;
                i++;
            }
            return result;
        }
    }
}

